The present invention relates to computerized graphics systems in general, and in particular to computerized graphics systems for rendering images of three-dimensional terrain.
Rendering terrain based on data representations of three-dimensional (3D) topographies for viewing on a computer display is known in the art. Typically, a three-dimensional terrain is represented as a collection of data points and stored in a data structure. Terrain rendering techniques generally apply some form of ray tracing to a set of data points. Known ray tracing techniques involve tracing a ray from the view point through each pixel in the display until the ray reaches the surface of the data. The primary disadvantage of ray tracing is that its implementation is quite slow, taking minutes or hours to produce an image of a single scene, even using state of the art hardware and software.
The present invention seeks to provide novel apparatus and methods for rendering three-dimensional terrains that do not require ray tracing for all data points in a viewable area. The present invention provides an improved system which overcomes the known disadvantages of the prior art as discussed above. The rendering is performed using a variation on known ray tracing techniques where a first ray is traced for a first display pixel, and adjacent pixels are calculated by moving the point of contact between the first ray and the surface of the data to a point on a ray that goes through an adjacent pixel. The point is then moved forward or backward along the new ray until it contacts the surface of the data.
There is thus provided in accordance with a preferred embodiment of the present invention a method for rendering a three-dimensional terrain, the method including providing at least one previous display pixel having a previous ray from a point of view through the at least one previous display pixel to a previous terrain unit intersecting an axis of the previous ray, the previous ray having a length, and computing a subsequent ray from the point of view through a subsequent display pixel, whereby the subsequent ray has a length equal to the length of the previous ray.
Further in accordance with a preferred embodiment of the present invention the providing step includes tracing the at least one previous ray through the at least one previous display pixel.
Still further in accordance with a preferred embodiment of the present invention the providing step includes previously computing the at least one previous ray.
Additionally in accordance with a preferred embodiment of the present invention the providing step includes providing a plurality of the previous display pixels, and wherein the computing step includes computing a subsequent ray the subsequent display pixel is adjacent to at least two of the plurality of the previous display pixels, and whereby the subsequent ray has a length equal to the shortest of the lengths of the previous rays of the plurality of previous display pixels to which the subsequent display pixel is adjacent.
Moreover in accordance with a preferred embodiment of the present invention the preceding claims and further including the step of maintaining any of the lengths in a Z-buffer, and the providing step includes retrieving any of the lengths from the Z-buffer.
Further in accordance with a preferred embodiment of the present invention the length of the subsequent ray is adjusted for a subsequent terrain unit intersecting an axis of the subsequent ray.
Still further in accordance with a preferred embodiment of the present invention the adjusting step includes comparing a position of a ray point at an end of the subsequent ray to an elevation of the subsequent terrain unit, correcting the length of the subsequent ray by either of increasing the length of the subsequent ray if the position of the ray point is above the subsequent terrain unit, and decreasing the length of the subsequent ray if the position of the ray point is below the subsequent terrain unit, and repeating the correcting step until the ray point is in propinquity to the subsequent terrain unit.
Additionally in accordance with a preferred embodiment of the present invention the repeating step includes repeating until the ray point is in propinquity to the subsequent terrain unit within a predetermined tolerance.
Moreover in accordance with a preferred embodiment of the present invention the correcting step includes increasing the length of the subsequent ray by a factor, and incrementing the factor by abase value subsequent to the increasing step.
Further in accordance with a preferred embodiment of the present invention the incrementing step includes providing the base value equal to Vr+2d, the Vr is equal to a unit vector value of the subsequent ray and d is equal to Log2 of the length of the subsequent ray.
Still further in accordance with a preferred embodiment of the present invention the correcting step includes decreasing the length of the subsequent ray by a base value.
Additionally in accordance with a preferred embodiment of the present invention the correcting step includes providing the base value equal to Vr+2d, the Vr is equal to a unit vector value of the subsequent ray and d is equal to Log2 of the length of the subsequent ray.
There is also provided in accordance with a preferred embodiment of the present invention a method of determining a scan direction, the method including providing a perspective axis passing through a view point and being substantially perpendicular to a data plane, the data plane includes a plurality of terrain units of a uniform elevation, providing a perspective point at an intersection of the perspective axis and a display plane of a display, rotating the perspective axis about the perspective point until the perspective axis lies in the display plane, thereby providing a longitudinal quadrant axis, providing a latitudinal quadrant axis perpendicular to the longitudinal quadrant axis and intersecting the longitudinal quadrant axis at the perspective point, and setting the scan direction as being either of away from the perspective point if the view point is above the perspective point, and toward the perspective point if the view point is below the perspective point.
Further in accordance with a preferred embodiment of the present invention either of the quadrant axes are moved in the display plane until the perspective point meets an edge of the display.
Still further in accordance with a preferred embodiment of the present invention either of the perspective axis and the display plane are adjusted until the perspective axis and the display plane intersect.
There is also provided in accordance with a preferred embodiment of the present invention a method of storing a terrain image in a data structure, the method including providing the terrain image in at least one resolution, dividing each resolution into at least one tile including at least one picture element.
Further in accordance with a preferred embodiment of the present invention either of a color attribute and an elevation attribute are stored for each of the picture elements.
Still further in accordance with a preferred embodiment of the present invention the dividing step includes providing the tile with a fixed number of the picture elements.
Additionally in accordance with a preferred embodiment of the present invention the providing the terrain image step includes providing a plurality of the resolutions and further including providing at least one pointer from a parent tile of a first of the plurality of the resolutions to a child tile of a second of the plurality of the resolutions, the first of the plurality of the resolutions is of lesser detail than the second of the plurality of the resolutions.
Moreover in accordance with a preferred embodiment of the present invention the first of the plurality of the resolutions has four times more detail than the second of the plurality of the resolutions.
There is also provided in accordance with a preferred embodiment of the present invention a method of storing terrain image tiles in a memory, the method including determining a currently viewed tile, reading at least one near tile contiguous to the currently viewed tile into the memory, dividing the currently viewed tile into a plurality of sections, determining a currently viewed section of the currently viewed tile, and reading at least one far tile not abutting the currently viewed tile into the memory, the far tile is at a predetermined orientation relative to the currently viewed section.
Further in accordance with a preferred embodiment of the present invention the reading at least one near tile step includes reading eight tiles the each of the eight tiles abuts the currently viewed tile.
Still further in accordance with a preferred embodiment of the present invention the dividing step includes dividing the currently viewed tile into four sections including top-left, top-right, bottom-left, and bottom-right sections.
Additionally in accordance with a preferred embodiment of the present invention the reading at least one far tile step includes reading a row of tiles parallel to an outer edge of the currently viewed section, the currently viewed section is intermediate to the row and another of the sections.
Moreover in accordance with a preferred embodiment of the present invention the reading at least one far tile step includes reading a column of tiles parallel to an outer edge of the currently viewed section, the currently viewed section is intermediate to the column and another of the sections.
Further in accordance with a preferred embodiment of the present invention the reading at least one far tile step includes reading a row of tiles parallel to an outer edge of the currently viewed section, the currently viewed section is intermediate to the row and another of the sections, and reading a column of tiles parallel to an outer edge of the currently viewed section, the currently viewed section is intermediate to the column and another of the sections.
Still further in accordance with a preferred embodiment of the present invention either of the reading a row step and the reading a column step includes reading three tiles.
Additionally in accordance with a preferred embodiment of the present invention a corner tile intersecting the row and the column is read.
Moreover in accordance with a preferred embodiment of the present invention any of the steps are performed for a plurality of resolution levels.
Further in accordance with a preferred embodiment of the present invention any of the reading steps includes reading into a disk cache memory.
There is also provided in accordance with a preferred embodiment of the present invention a method of managing terrain image tiles in a memory, the method including maintaining an index including a coordinate of each of a plurality of stored tiles and a pointer to each of the plurality of stored tiles, searching the index for an index entry matching a coordinate of a requested tile, incrementing a plurality of use counters for a rendering cycle, each of the plurality of use counters corresponding to a one of the plurality of stored tiles, if the coordinate of the requested tile is found in the index returning the pointer to the stored tile the coordinate of the stored tile matches the coordinate of the requested tile, and zeroing the use counter corresponding to the stored tile the coordinate of the stored tile matches the coordinate of the requested tile, and if the coordinate of the requested tile is not found in the index determining a least recently used stored tile whose use counter is highest among the plurality of use counters, and reading the requested tile into the memory, whereby the least recently used stored tile is replaced with the requested tile.
Further in accordance with a preferred embodiment of the present invention the maintaining an index step includes maintaining an index of at least one bit of each of the coordinates of the plurality of stored tiles.
Still further in accordance with a preferred embodiment of the present invention the maintaining an index step includes maintaining an index of 5 least-significant bits of each of the coordinates of the plurality of stored tiles.
Additionally in accordance with a preferred embodiment of the present invention the searching step includes searching using at least one bit of the coordinate of the requested tile.
Moreover in accordance with a preferred embodiment of the present invention the maintaining an index step includes maintaining an index of at least one bit of each of the coordinates of the plurality of stored tiles, the searching step includes searching using at least one bit of the coordinate of the requested tile, and if the at least one bit of coordinate of the requested tile is found in the index, further including verifying that a fill coordinate of the requested tile matches a full coordinate of the stored tile corresponding to the index entry.
Further in accordance with a preferred embodiment of the present invention, if the coordinate of the requested tile is not found in the index, a disk cache memory is saerched for the requested tile and the reading step includes reading the requested tile from the disk cache memory.
There is also provided in accordance with a preferred embodiment of the present invention three-dimensional terrain rendering apparatus including a display having a plurality of pixels, a memory for recording a relationship between at least one previous display pixel, a previous ray from a point of view through the at least one previous display pixel to a previous terrain unit intersecting an axis of the previous ray, and a length of the previous ray, and apparatus for computing a subsequent ray from the point of view through a subsequent display pixel given the relationship, whereby the subsequent ray has a length equal to the length of the previous ray.